// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 使用滚动数组进行优化：删除横坐标，从右往左填表

// 例题 4:
// 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
//
//        每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
//
//        如果 x == y，那么两块石头都会被完全粉碎；
//        如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
//        最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
//
//        示例 1：
//
//        输入：stones = [2,7,4,1,8,1]
//        输出：1
//        解释：
//        组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
//        组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
//        组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
//        组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
//        示例 2：
//
//        输入：stones = [31,26,33,21,40]
//        输出：5
//
//
//        提示：
//
//        1 <= stones.length <= 30
//        1 <= stones[i] <= 100


// 解题思路:
// 最复杂的是分析思路：可以想象把石头分为两堆，当两堆石头重量接近的时候，才能得到最小值，所以考虑选一堆石头，重量接近 sum / 2
// dp[i][j] [0, i] 区间内选石头，和最接近 j 的石头重量
// if(j >= nums[i]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]])
// else dp[i][j] = dp[i - 1][j]
// 返回 sum - 2 * dp[n][sum / 2]

public class LastStoneWeightII {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int x : stones) sum += x;
        int t = sum / 2;

        int[][] dp = new int[n + 1][t + 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= t; j++){
                if(j >= stones[i - 1]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return sum - 2 * dp[n][t];
    }
}
